---
title: 语言处理程序
description: 编译程序基本原理、文法定义、正规式、有限自动机、语法分析方法
---
## 编译过程基本原理


编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中的一些相关符号的类型和特征等信息，并将其存入到符号表中，编译过程如下：


<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241101235015.png"/>

### 词法分析
是编译过程的第一个阶段。这个阶段的任务是 <RedSpan>从左到右一个字符一个字符地读入程序</RedSpan>，即对构成源程序的 <RedSpan>字符流进行扫描然后根据构词规则识别单词</RedSpan>（也称单词符号或符号）。

### 语法分析
是编译过程的一个逻辑阶段。语法分析的任务是 <RedSpan>在词法分析的基础上将单词序列组合成各类语法短语</RedSpan>，如“程序”，“语句”，“表达式”等等，语法分析程序判断源程序在结构上是否正确。

:::tip
语法分析阶段的主要任务是对各条语句的结构进行合法性分析，比如括号不匹配。
:::

### 语义分析
是编译过程的一个逻辑阶段，语法分析的任务是 <RedSpan>对结构上正确的源程序进行上下文有关性质的审查，进行类型审查</RedSpan>。如果类型匹配、除法除数不为 0 等。又分为 <RedSpan>静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）</RedSpan>。

### 中间代码生成
中间代码是根据 <RedSpan>语义分析产生的</RedSpan>，需要 <RedSpan>经过优化链接，最终生成可执行的目标代码。</RedSpan>引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有 <RedSpan>后缀式（逆波兰式）、三元式（三地址码）、四元式和树等形式</RedSpan>。需要考虑三个问题(一是 <RedSpan>如何生成较短的目标代码；而是如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；三是如何充分利用计算机指令系统的特点，以提高目标代码的质量</RedSpan>)。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241102135219.png"/>

* 前缀表达式：+ab
* 中缀表达式：a+b
* 后缀表达式：ab+

主要掌握上述三种表达式即可，其实就是树的三种遍历，一般 <RedSpan>正常的表达式是中序遍历</RedSpan>，即中缀表达式，根据其构造出树，再按题目要求写出前缀和后缀式。

简单求法：后缀表达式是<RedSpan>从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面</RedSpan>。再去掉所有的括号。


## 文法
文法用在编译中
### 字母表、字符串、字符串集合
* 字母表 $\sum$ 和字符：字母表是字符的非空有穷集合，字母是字母表 $\sum$ 中的元素。例如 $\sum$ = $\{a,b\}$,a 或 b 是字符。
* 字符串：$\sum$ 中字符组成的有穷序列。例如 a,ab,aaa 都是 $\sum$ 上的字符串。
* 字符串的长度：指字符串中字符的个数。如 $|aba|=3$。
* 空串 $\varepsilon$: 由零个字符组成的序列，$|\varepsilon|=0$
* 连接：字符串 S 和 T 的连接是指将串 T 接续在串 S 之后，表示为 S·T,连接符号 “·” 可省略。
* $\sum^*$: 是指空串 $\varepsilon$ 在内的 $\sum$ 上所有字符串的集合。例如： $\sum=\{a,b\}$, $\sum^*=\{\varepsilon,a,b,aa,bb,ab,ba,aaa,...\}$
* 字符串的方幂：把字符串 $\alpha$ 自身连接 n 次得到的串，称为字符串 $\alpha$ 的 n 次方幂，记为 $\alpha^n$,$\alpha_0=\varepsilon$,$aa^{n-1}=a^{n-1}a(n>0)$

### 字符串集合上的运算
设 A，B 代表字母表 $\sum$ 上的两个字符串集合。
* 或（合并）：$A \cup B=\{\alpha|\alpha \in A \,or\, \alpha \in B\}$
* 积（连接）：$A \cap B=\{\alpha\beta|\alpha \in A \,and\, \beta \in B\}$
* 幂：$A^n=A·A^{n-1}=A^{n-1}·A$,并规定 $A^0=\{\varepsilon\}$
* 正则闭包+：$A^+=A^1 \cup A^2 \cup A^3 \cup ... \cup A^n...$
* 闭包*：$A^*=A^0+A^+$,显然 $\sum^+=\sum^u \cup \sum^1 \cup \sum^2 \cup ... \cup \sum^n...$

### 文法定义
文法 G 是一个四元组，可表示为 G=(V,T,P,S),其中：
* V: 非终结符，不是语言组成部分，不是最终结构，可以推导出其他元素。
* T： 终结符：是语言的组成部分，是最终结果，不能再推导其它元素。
* S： 起始符, 是语言的开始符号。
* P： 产生式。用终结符代替非终结符的规则，例如 a->b

乔姆斯基把文法分为 4 种类型，即 0 型、1 型 、2 型和 3 型。
* 0 型文法也称为短语文法，其概念相当于图灵机，任何 0 型语言都是递归可枚举的；反之，递归可枚举的也必定是一个 0 型语言。
* 1 型文法也称为 <RedSpan>上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文</RedSpan>，并且一般不允许替换为 $\varepsilon$ 串。例如，若 $\alpha A \beta \rightarrow \alpha \gamma \beta$ 是 1 型文法的产生式，$\alpha$ 和  $\beta$ 不全为空，则非终结符 A 只有在左边是 $\alpha$,右边是 $\beta$ 的上下文中才能替换成 $\gamma$。
* 2 型文法就是 <RedSpan>上下文无关文法，非终结符的替换无需考虑上下文。程序设计语言中大部分语法都是上下文无关文法</RedSpan>，当然语义上是相关的，要注意区分语法和语义。
* <RedSpan>3 型文法等价于正规式</RedSpan>，因此也称为正规文法或线性文法。

## 正规式
语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

<RedSpan>词法规则可用 3 型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集 $\sum$(字母表) 上字符串的一个子集，称为正规集。</RedSpan>

### 正规式和正规集
对于字母表 $\sum$ ，其上的正规式及其表示的正规集可以递归定义如下：
1. $\varepsilon$ 是一个正规式，它表示集合 $L(\varepsilon)=\{\varepsilon\}$。
2. 若 $\alpha$ 是 $\sum$ 上的字符，则 $\alpha$ 是一个正规式，它所表示的正规集为 $\{\alpha\}$。
3. 若正规式 r 和 s 分别表示正规集 L(r) 和 L(s),则：
    1. `r|s` 是正规式，表示集合 $L(r) \cup L(s)$
    2. `r·s` 是正规式，表示集合 $L(r)L(s)$
    3. $r^*$ 是正规式，表示集合 $L(r)^*)$
    4. (r) 是正规式，表示集合 $L(r)$

仅通过 <RedSpan>有限次使用上述 3 个步骤定义的表达式才是 $\sum$上的正规式，其中，运算符 “`|`”，“`·`”，“`*`”
分别称为“或”，“连接” 和 “闭包”</RedSpan>在正规式的书写中，
连接运算符 “·” 可以胜利，运算的优先级从高到低排列为“*” “·” “`|`”。

设 $\sum = \{a,b\}$，下表列出了 $\sum$ 上的一些正规式和相应的正规集。

| 正规式           | 正规集                  |
|---------------|----------------------|
| ab            | 字符串 ab 构成的集合         |
| a\|b          | 字符串a、b 构成的集合         |
| $a^*$         | 由 0 个或多个 a 构成的字符串集合  |
| $(a\|b)^*$    | 所有字符 a 和 b 构成的串的集合   |
| $a(a\|b)^*$   | 以 a 为首字符的 a、b 字符串的集合 |
| $(a\|b)^*abb$ | 以 abb 结尾的 a、b 字符串的集合 |

## 有限自动机
有限自动机是一种识别装置的抽象概念，它能 <RedSpan>准确是被正规集</RedSpan>。有限自动机分为确定的有限自动机和不确定的有限自动机两类。

### 确定的有限自动机 DFA
一个确定的有限自动机是个五元组（S,$\sum$,f,$s_0$,Z）,其中：
* S 是一个有限集，其每个元素称为一个状态。
* $\sum$ 是一个有穷字母表，其每个元素称为一个输入字符。
* f 是 S x $\sum$ 上的单值部分映像。f(A,a) = Q 表示当前状态为 A、输入为 a 时，将转换到下一状态 Q。称 Q 是 A 的一个后继状态。
* $s_0 \in S$， 是唯一的一个开始状态。
* Z 是非空的终止状态集合， $Z \subseteq S$。

状态转换图示例如下：
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241102162759.png"/>

### 不确定的有限自动机 NFA
一个不确定的有限自动机也是一个五元组，它与确定的有限自动机区别如下：

1. f 是 $S \times \sum \rightarrow 2S$上的映像，对于 S 中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后续状态不一定是唯一的。
2. 有向弧上的标记可以是 $\varepsilon$。

确定的有限自动机和不确定的有限自动机：<RedSpan>输入一个字符，看是否能得出唯一的后继</RedSpan>，若能，则是确定的，否则若得出多个后继，则是不确定的。


<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241102202920.png"/>

## 语法分析方法
### 自上而下语法分析
<RedSpan>最左推导、从左至右</RedSpan>。给定文法 G 和源程序串 r，从 G 的开始符号 S 触发，通过反复使用产生式对句型中的非终结符进行替换（推导），逐步推导出 r。

<RedSpan>递归下降思想</RedSpan>：原理是利用函数之间的 <RedSpan>递归调用模拟语法树自上而下的构造过程</RedSpan>，是一种自上而下的语法分析方法。

### 自下而上语法分析

<RedSpan>最右推导，从右至左</RedSpan>。从给定的输入串 r 开始，不断寻找子串与文法 G 中某个产生式 P 的候选式进行匹配，并用 P 的左部代替（归约）之，逐步归约到开始符号 S。

<RedSpan>移进-归约思想</RedSpan>：设置一个栈，将输入符号逐步移入到栈中，栈顶形成某产生式的右部时，就用左部代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。

